package 金明的预算方案;

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int N = 70, M = 32010;
    static int[] f = new int[M];
    static PII[] master = new PII[M];
    static ArrayList<PII>[] servant = new ArrayList[N];//表示附件

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        for (int i = 1; i <= n; i++) {
            servant[i] = new ArrayList<>();
        }
        for (int i = 1; i <= n; i++) {
            int v = in.nextInt();
            int w = in.nextInt();
            int p = in.nextInt();
            if (p == 0) {
                master[i] = new PII(v, v * w);
            } else {
                servant[p].add(new PII(v, v * w));
            }
        }
        for (int i = 1; i <= n; i++) {
            if (master[i] != null) {
                for (int j = m; j >= 1; j--) {
                    for (int k = 0; k < 1 << servant[i].size(); k++) {
                        int v = master[i].v;
                        int w = master[i].w;
                        for (int u = 0; u < servant[i].size(); u++) {
                            if ((k >> u & 1) == 1) {
                                v += servant[i].get(u).v;
                                w += servant[i].get(u).w;
                            }
                        }
                        if (j >= v) {
                            f[j] = Math.max(f[j], f[j - v] + w);
                        }
                    }
                }
            }
        }
        System.out.println(f[m]);
    }
}

class PII {
    int v, w;

    public PII(int v, int w) {
        this.v = v;
        this.w = w;
    }
}